package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 304. 二维区域和检索 - 矩阵不可变
 * 剑指 Offer II 013. 二维子矩阵的和
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/15 10:40
 */
public class NumMatrix {

    int[][] presum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] arr = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        this.presum = arr;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2 + 1][col2 + 1] + presum[row1][col1] - presum[row1][col2 + 1] - presum[row2 + 1][col1];
    }
}
